package leetcode.N1301_N1400;

import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/11/25 4:44 下午
 */
public class N1370 {

    public static void main(String[] args) {
        String s = "aaaabbbbcccc";
        N1370 n = new N1370();
        System.out.println(n.sortString(s));
    }


    public String sortString(String s) {
        TreeMap<Character, Integer> mapping = new TreeMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            Integer oldValue = mapping.getOrDefault(c, 0);
            mapping.put(c, oldValue + 1);
        }

        boolean needReverse = false;
        StringBuilder result = new StringBuilder();
        StringBuilder sb = new StringBuilder();
        int length = 0;
        while (length < s.length()) {
            Iterator<Map.Entry<Character, Integer>> iterator = mapping.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<Character, Integer> next = iterator.next();
                sb.append(next.getKey());
                length++;
                Integer oldValue = next.getValue();
                if (oldValue == 1) {
                    iterator.remove();
                } else {
                    next.setValue(oldValue - 1);
                }
            }
            if (needReverse) {
                result.append(sb.reverse());
            } else {
                result.append(sb);
            }
            sb.setLength(0);
            needReverse = !needReverse;
        }
        return result.toString();
    }

}
